# 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
# n<=39
storage = [_ for _ in range(40)]
def Febio(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    elif n > 39:
        print('你骗人！明明说好了n<=39的，哼！')
        return
    else:
        storage[n] = Febio(n - 1) + Febio(n - 2)
    return storage[n]

print(Febio(30))
# 这个方法是没有问题的，但是在网站上依然超时，可能是由于对方用的是python2.x的缘故吧，也可能对方配置不行，下面用for循环来解
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 1
        if n >= 3:
            s = []*n
            s.append(1)
            s.append(1)
            for i in range(2,n):
                s.append(s[i-1]+s[i-2])
            return s[n-1]